This invention relates to message routing in computer networks and, more particularly, to resolving issues of priority in network message transmissions.
Signal transmission networks generally receive input signals from a source, transmit those signals along a network of paths that are internally connected at nodes, and output the signal at the desired location. When substantial use of the network is occurring two or more messages may arrive at a network node and require the same output path for retransmission of the messages to their respective destinations. When this happens, the node must be capable of determining the message that will be first connected to the output path, i.e., conflict resolution must occur.
There are two types of critical properties that can be associated with these priority schemes. The first is "flushability": a routing scheme is flushable in time T if, given any configuration of packets in the network and no more packets entering the network, all packets in the network exit within time T. The second is associated with "livelock": a routing scheme is livelock free if there is a constant S such that any packet entering the network is guaranteed to reach its destination in time S. Clearly, a livelock free network must be flushable and S.gtoreq.T.
There are many different schemes for conflict resolution along computer networks. In an oblivious router, an input frame is immediately routed to the output frame for the preferred path to the message destination. If the output frame is not available, the message is held in the input frame until the desired output frame becomes available. Succeeding messages are delayed until the message in the input frame is transmitted.
In a deflection router, messages arriving at a node are guaranteed to leave the node in the next routing cycle. If possible, each message is assigned to an output channel that reduces the distance to the destination, with priority given to messages with only a single profitable direction. Any remaining messages are randomly assigned to the remaining free output channels. Thus, messages are deflected and delayed within the system until they arrive at a node with no conflict or have only a single profitable direction from which to leave a node.
Another router is the chaos router where messages include a routing header that determines a set of equally profitable channels from which the message might leave a node. The first available channel is selected for routing. Messages that do not have an available profitable channel are stored in a small buffer queue and the first message in the queue that can profitably use an available output channel is assigned to that channel. If the queue is completely full, the next incoming message will cause a message to be randomly selected from the queue and derouted along the first available channel to create room for the newly arriving message.
Desparation routing (often called "hot potato" routing) is a resource efficient method of adaptive routing in packet switching communication networks. Examples of classes of priority schemes are collision counting and distance routing. Collision counting involves incrementing a counter each time a packet is misrouted. In resolving conflicts, some function of the counter has priority (equality is resolved randomly). In distance routing schemes, conflicts are resolved by measuring priority with some function of the distance a packet has remaining to its destination.
In one variation of the collision counting scheme, the collision counter is used to directly assign priority, but when the collision counter reaches a selected maximum value, the packet goes "Eulerian", i.e., the packet follows a predetermined Eulerian path that traverses each wire of the network once and only once. This scheme is flushable and livelock free, but has two flaws: first, any packet that goes Eulerian must follow the Eulerian path even if shorter paths to the destination become available, incurring a large unneeded time penalty; second, Eulerian packets are undesirable so the counter is set to a large count thereby adding many unwanted bits to the message packet header.
Accordingly, it is an object of the present invention to provide a livelock free priority assignment system that requires only a minimum number of priority bits in a message header.
It is another object of the present invention to minimize the time penalty associated with a livelock-free system.
Yet another object of the present invention is to provide that all messages will exit a transmission network within a known time.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.